package com.jugheadzhou.practice.leecode;

import java.util.Arrays;
import java.util.Random;

public class FastSort {
    public static int[] sortArray(int[] nums) {
        if (nums.length < 2){
            return nums;
        }

        fastSort(nums, 0, nums.length - 1);
        return nums;
    }

    private static void fastSort(int[] nums, int low, int high) {
        if (low >= high){
            return;
        }
        Random random = new Random();

        int baseVal = nums[low];
        int l = low;
        int r = high;
        int temp = 0;
        while (l < r){
            while (nums[r] >= baseVal && l < r){
                r--;
            }
            while (nums[l] <= baseVal && l < r){
                l++;
            }

            if (l < r){
                temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
            }
        }
        // 交换基本数
        nums[low] = nums[l];
        nums[l] = baseVal;
        // 4. 根据条件左侧递归遍历
        if (low < l) {
            fastSort(nums, low, l - 1);
        }
        // 5. 根据条件右侧递归遍历
        if (r < high) {
            fastSort(nums, r + 1, high);
        }
    }

    public static void quickSort(int[] array, int low, int high) {
        if (low >= high) {
            return;
        }
        int pivot = array[low];
        int l = low;
        int r = high;
        int temp = 0;
        while (l < r) {
            while (l < r && array[r] >= pivot) {
                r--;
            }
            while (l < r && array[l] <= pivot) {
                l++;
            }
            if (l < r) {
                temp = array[l];
                array[l] = array[r];
                array[r] = temp;
            }
        }
        array[low] = array[l];
        array[l] = pivot;
        if (low < l) {
            quickSort(array, low, l - 1);
        }
        if (r < high) {
            quickSort(array, r + 1, high);
        }

    }



    public static void main(String[] args) {
        int[] nums = {5,2,3,1};
//        FastSort.quickSort(nums, 0, nums.length - 1);
        FastSort.fastSort(nums, 0, nums.length - 1);
        System.out.println("ints = " + Arrays.toString(nums));


    }

}
